package com.leetcode.algorithm.y22.m06;

/**
 * 1314. 矩阵区域和
 * 
 * https://leetcode.cn/problems/matrix-block-sum/
 * 
 * @author jie.deng
 *
 */
class Question1314Solution01 {

	public int[][] matrixBlockSum(int[][] mat, int k) {
		int m = mat.length;
		int n = mat[0].length;
		// 前缀和
		// prefixSumArr[i][j] = mat[0...i][0...j]所有元素的和
		int[][] prefixSumArr = new int[m][n];
		prefixSumArr[0][0] = mat[0][0];
		// 第1行前缀和
		for (int j = 1; j < n; j++) {
			prefixSumArr[0][j] = prefixSumArr[0][j - 1] + mat[0][j];
		}
		// 第1列前缀和
		for (int i = 1; i < m; i++) {
			prefixSumArr[i][0] = prefixSumArr[i - 1][0] + mat[i][0];
		}
		// 其他行列的前缀和
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				prefixSumArr[i][j] = prefixSumArr[i - 1][j] + prefixSumArr[i][j - 1] - prefixSumArr[i - 1][j - 1]
						+ mat[i][j];
			}
		}

		int[][] answer = new int[m][n];
		for (int i = 0; i < m; i++) {
			int rMin = Math.max(i - k, 0);
			int rMax = Math.min(i + k, m - 1);
			for (int j = 0; j < n; j++) {
				int cMin = Math.max(j - k, 0);
				int cMax = Math.min(j + k, n - 1);
				answer[i][j] = prefixSumArr[rMax][cMax];
				if (rMin > 0) {
					answer[i][j] -= prefixSumArr[rMin - 1][cMax];
				}
				if (cMin > 0) {
					answer[i][j] -= prefixSumArr[rMax][cMin - 1];
				}
				if (cMin > 0 && rMin > 0) {
					answer[i][j] += prefixSumArr[rMin - 1][cMin - 1];
				}
			}
		}
		return answer;
	}

}